package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202408;

public class leetcode20240828 {
    public int minimumSubstringsInPartition(String s){
        char[] chs=s.toCharArray();
        int n=chs.length;
        int[] memo=new int[n];
        return dfs(n-1,chs,memo);
    }

    private int dfs(int i,char[] chs,int[] memo){
        if(i<0){
            return 0;
        }
        if(memo[i]>0){
            return memo[i];
        }
        int res=Integer.MAX_VALUE;
        int[] cnt=new int[26];
        int k=0,maxCnt=0;
        for(int j=i;j>=0;j--){
            k+=cnt[chs[j]-'a']++ == 0 ? 1 : 0;
            maxCnt=Math.max(maxCnt,cnt[chs[j]-'a']);
            if(i-j+1==k*maxCnt){
                res=Math.min(res,dfs(j-1,chs,memo)+1);
            }
        }
        memo[i]=res;
        return res;
    }

}
